package cn.initcap.algorithm.swing.sort.threeway;

import cn.initcap.algorithm.swing.AlgoVisHelper;
import cn.initcap.algorithm.swing.BaseAlgoFrame;
import java.awt.EventQueue;
import java.awt.Graphics;
import java.awt.Graphics2D;

/**
 * @author initcap
 * @date 8/1/19 12:09 PM
 */
public class AlgoVisualizer {

    private static int DELAY = 20;
    private ThreeWaysQuickSortData data;
    private BaseAlgoFrame frame;

    public AlgoVisualizer(int sceneWidth, int sceneHeight, int n, ThreeWaysQuickSortData.Type dataType) {

        // 初始化数据
        data = new ThreeWaysQuickSortData(n, sceneHeight, dataType);

        // 初始化视图
        EventQueue.invokeLater(() -> {
            frame = new BaseAlgoFrame("Three Ways Quick Sort Visualization", sceneWidth, sceneHeight) {
                @Override
                public void draw(Graphics graphics) {
                    Graphics2D g2d = (Graphics2D) graphics;
                    int w = sceneWidth / data.N();
                    for (int i = 0; i < data.N(); i++) {
                        if (i >= data.l && i <= data.r) {
                            AlgoVisHelper.setColor(g2d, AlgoVisHelper.GREEN);
                        } else {
                            AlgoVisHelper.setColor(g2d, AlgoVisHelper.GREY);
                        }

                        if (i == data.curPivot) {
                            AlgoVisHelper.setColor(g2d, AlgoVisHelper.INDIGO);
                        }
                        if (i >= data.l + 1 && i <= data.curL) {
                            AlgoVisHelper.setColor(g2d, AlgoVisHelper.LIGHT_BLUE);
                        }
                        if (i >= data.curR && i <= data.r) {
                            AlgoVisHelper.setColor(g2d, AlgoVisHelper.LIGHT_BLUE);
                        }
                        if (data.fixedPivots[i]) {
                            AlgoVisHelper.setColor(g2d, AlgoVisHelper.RED);
                        }

                        AlgoVisHelper.fillRectangle(g2d, i * w, sceneHeight - data.get(i), w - 1, data.get(i));
                    }
                }
            };

            new Thread(() -> {
                run();
            }).start();
        });
    }

    public AlgoVisualizer(int sceneWidth, int sceneHeight, int n) {
        this(sceneWidth, sceneHeight, n, ThreeWaysQuickSortData.Type.Default);
    }

    public static void main(String[] args) {

        int sceneWidth = 800;
        int sceneHeight = 800;
        int n = 100;

        new AlgoVisualizer(sceneWidth, sceneHeight, n, ThreeWaysQuickSortData.Type.Default);

    }

    public void run() {

        setData(-1, -1, -1, -1, -1, -1);

        quickSort3Ways(0, data.N() - 1);

        setData(-1, -1, -1, -1, -1, -1);
    }

    private void quickSort3Ways(int l, int r) {

        if (l > r) {
            return;
        }

        if (l == r) {
            setData(l, r, l, -1, -1, -1);
            return;
        }

        setData(l, r, -1, -1, -1, -1);

        // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
        int p = (int) (Math.random() * (r - l + 1)) + l;
        setData(l, r, -1, p, -1, -1);

        data.swap(l, p);
        int v = data.get(l);
        setData(l, r, -1, l, -1, -1);

        // arr[l+1...lt] < v
        int lt = l;
        // arr[gt...r] > v
        int gt = r + 1;
        // arr[lt+1...i) == v
        int i = l + 1;
        setData(l, r, -1, l, lt, gt);

        while (i < gt) {
            if (data.get(i) < v) {
                data.swap(i, lt + 1);
                i++;
                lt++;
            } else if (data.get(i) > v) {
                data.swap(i, gt - 1);
                gt--;
            } else // arr[i] == v
            {
                i++;
            }

            setData(l, r, -1, l, i, gt);
        }

        data.swap(l, lt);
        setData(l, r, lt, -1, -1, -1);

        quickSort3Ways(l, lt - 1);
        quickSort3Ways(gt, r);
    }

    private void setData(int l, int r, int fixedPivot, int curPivot, int curL, int curR) {
        data.l = l;
        data.r = r;
        if (fixedPivot != -1) {
            data.fixedPivots[fixedPivot] = true;
            int i = fixedPivot;
            while (i < data.N() && data.get(i) == data.get(fixedPivot)) {
                data.fixedPivots[i] = true;
                i++;
            }
        }
        data.curPivot = curPivot;
        data.curL = curL;
        data.curR = curR;

        frame.render(data);
        AlgoVisHelper.pause(DELAY);
    }
}